package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Administrator
 * @date 2019/11/27 10:29
 */
public class GuessNumber {
    /**
     * 从 1 到 n 之间选择一个数字，猜选了哪个数字。
     * 每次猜错了，被告知选的数字比猜的大了或者小了。
     * 当猜了数字 x 并且猜错了的时候，需要支付金额为 x 的现金。
     * 直到猜到选的数字，才算赢得了这个游戏。
     */
    @Test
    public void test() {
        Assert.assertEquals(16, getMoneyAmount(10));
        Assert.assertEquals(0, getMoneyAmount(1));
    }

    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 1];

        for (int len = 2; len <= n; len++) {
            for (int start = 1; start <= n - len + 1; start++) {
                int minres = Integer.MAX_VALUE;
                for (int piv = start + (len - 1) / 2; piv < start + len - 1; piv++) {
                    int res = piv + Math.max(dp[start][piv - 1], dp[piv + 1][start + len - 1]);
                    minres = Math.min(res, minres);
                }
                dp[start][start + len - 1] = minres;
            }

        }
        return dp[1][n];
    }
}
